/*
    * Copyright (C) 2010 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
    * in compliance with the License. You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
    * Unless required by applicable law or agreed to in writing, software distributed under the License
   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
   * or implied. See the License for the specific language governing permissions and limitations under
   * the License.
   */
  
  package com.google.common.collect;
  
  import static com.google.common.base.Preconditions.checkNotNull;
  
  import com.google.common.annotations.Beta;
  import com.google.common.annotations.GwtCompatible;
  import com.google.common.base.Function;
  
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.List;
  import java.util.RandomAccess;
  
  import javax.annotation.Nullable;
  
  /**
   * Static methods pertaining to sorted {@link List} instances.
   *
   * In this documentation, the terms <i>greatest</i>, <i>greater</i>, <i>least</i>, and
   * <i>lesser</i> are considered to refer to the comparator on the elements, and the terms
   * <i>first</i> and <i>last</i> are considered to refer to the elements' ordering in a
   * list.
   *
   * @author Louis Wasserman
   */
  @GwtCompatible
  @Beta final class SortedLists {
    private SortedLists() {}
  
    /**
     * A specification for which index to return if the list contains at least one element that
     * compares as equal to the key.
     */
    public enum KeyPresentBehavior {
      /**
       * Return the index of any list element that compares as equal to the key. No guarantees are
       * made as to which index is returned, if more than one element compares as equal to the key.
       */
      ANY_PRESENT {
        @Override
        <E> int resultIndex(
            Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
          return foundIndex;
        }
      },
      /**
       * Return the index of the last list element that compares as equal to the key.
       */
      LAST_PRESENT {
        @Override
        <E> int resultIndex(
            Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
          // Of course, we have to use binary search to find the precise
          // breakpoint...
          int lower = foundIndex;
          int upper = list.size() - 1;
          // Everything between lower and upper inclusive compares at >= 0.
          while (lower < upper) {
            int middle = (lower + upper + 1) >>> 1;
            int c = comparator.compare(list.get(middle), key);
            if (c > 0) {
              upper = middle - 1;
            } else { // c == 0
              lower = middle;
            }
          }
          return lower;
        }
      },
      /**
       * Return the index of the first list element that compares as equal to the key.
       */
      FIRST_PRESENT {
        @Override
        <E> int resultIndex(
            Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
          // Of course, we have to use binary search to find the precise
          // breakpoint...
          int lower = 0;
          int upper = foundIndex;
          // Of course, we have to use binary search to find the precise breakpoint...
          // Everything between lower and upper inclusive compares at <= 0.
          while (lower < upper) {
            int middle = (lower + upper) >>> 1;
            int c = comparator.compare(list.get(middle), key);
           if (c < 0) {
             lower = middle + 1;
           } else { // c == 0
             upper = middle;
           }
         }
         return lower;
       }
     },
     /**
      * Return the index of the first list element that compares as greater than the key, or {@code
      * list.size()} if there is no such element.
      */
     FIRST_AFTER {
       @Override
       public <E> int resultIndex(
           Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
         return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1;
       }
     },
     /**
      * Return the index of the last list element that compares as less than the key, or {@code -1}
      * if there is no such element.
      */
     LAST_BEFORE {
       @Override
       public <E> int resultIndex(
           Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
         return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1;
       }
     };
     abstract <E> int resultIndex(
         Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex);
   }
 
   /**
    * A specification for which index to return if the list contains no elements that compare as
    * equal to the key.
    */
   public enum KeyAbsentBehavior {
     /**
      * Return the index of the next lower element in the list, or {@code -1} if there is no such
      * element.
      */
     NEXT_LOWER {
       @Override
       int resultIndex(int higherIndex) {
         return higherIndex - 1;
       }
     },
     /**
      * Return the index of the next higher element in the list, or {@code list.size()} if there is
      * no such element.
      */
     NEXT_HIGHER {
       @Override
       public int resultIndex(int higherIndex) {
         return higherIndex;
       }
     },
     /**
      * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at
      * which the key would be inserted into the list: the index of the next higher element in the
      * list, or {@code list.size()} if there is no such element.
      *
      * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
      * list that compares as equal to the key.
      *
      * <p>This is equivalent to the behavior of
      * {@link java.util.Collections#binarySearch(List, Object)} when the key isn't present, since
      * {@code ~insertionIndex} is equal to {@code -1 - insertionIndex}.
      */
     INVERTED_INSERTION_INDEX {
       @Override
       public int resultIndex(int higherIndex) {
         return ~higherIndex;
       }
     };
 
     abstract int resultIndex(int higherIndex);
   }
 
   /**
    * Searches the specified naturally ordered list for the specified object using the binary search
    * algorithm.
    *
    * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
    * KeyAbsentBehavior)} using {@link Ordering#natural}.
    */
   public static <E extends Comparable> int binarySearch(List<? extends E> list, E e,
       KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) {
     checkNotNull(e);
     return binarySearch(
         list, checkNotNull(e), Ordering.natural(), presentBehavior, absentBehavior);
   }
 
   /**
    * Binary searches the list for the specified key, using the specified key function.
    *
    * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
    * KeyAbsentBehavior)} using {@link Ordering#natural}.
    */
   public static <E, K extends Comparable> int binarySearch(List<E> list,
       Function<? super E, K> keyFunction, @Nullable K key, KeyPresentBehavior presentBehavior,
       KeyAbsentBehavior absentBehavior) {
     return binarySearch(
         list,
         keyFunction,
         key,
         Ordering.natural(),
         presentBehavior,
         absentBehavior);
   }
 
   /**
    * Binary searches the list for the specified key, using the specified key function.
    *
    * <p>Equivalent to
    * {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)} using
    * {@link Lists#transform(List, Function) Lists.transform(list, keyFunction)}.
    */
   public static <E, K> int binarySearch(
       List<E> list,
       Function<? super E, K> keyFunction,
       @Nullable K key,
       Comparator<? super K> keyComparator,
       KeyPresentBehavior presentBehavior,
       KeyAbsentBehavior absentBehavior) {
     return binarySearch(
         Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
   }
 
   /**
    * Searches the specified list for the specified object using the binary search algorithm. The
    * list must be sorted into ascending order according to the specified comparator (as by the
    * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior
    * to making this call. If it is not sorted, the results are undefined.
    *
    * <p>If there are elements in the list which compare as equal to the key, the choice of
    * {@link KeyPresentBehavior} decides which index is returned. If no elements compare as equal to
    * the key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
    *
    * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
    * access to each list element.
    *
    * @param list the list to be searched.
    * @param key the value to be searched for.
    * @param comparator the comparator by which the list is ordered.
    * @param presentBehavior the specification for what to do if at least one element of the list
    *        compares as equal to the key.
    * @param absentBehavior the specification for what to do if no elements of the list compare as
    *        equal to the key.
    * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
    *         otherwise the index determined by the {@code KeyAbsentBehavior}.
    */
   public static <E> int binarySearch(List<? extends E> list, @Nullable E key,
       Comparator<? super E> comparator, KeyPresentBehavior presentBehavior,
       KeyAbsentBehavior absentBehavior) {
     checkNotNull(comparator);
     checkNotNull(list);
     checkNotNull(presentBehavior);
     checkNotNull(absentBehavior);
     if (!(list instanceof RandomAccess)) {
       list = Lists.newArrayList(list);
     }
     // TODO(user): benchmark when it's best to do a linear search
 
     int lower = 0;
     int upper = list.size() - 1;
 
     while (lower <= upper) {
       int middle = (lower + upper) >>> 1;
       int c = comparator.compare(key, list.get(middle));
       if (c < 0) {
         upper = middle - 1;
       } else if (c > 0) {
         lower = middle + 1;
       } else {
         return lower + presentBehavior.resultIndex(
             comparator, key, list.subList(lower, upper + 1), middle - lower);
       }
     }
     return absentBehavior.resultIndex(lower);
   }
 }